import java.util.ArrayList;

public class Sortowanko {
    private ArrayList<Wezelek>  sorted;

    public static void main(String a[]) {
        ArrayList<Wezelek> data = new ArrayList<Wezelek>();

        data.add(new Wezelek(1, 1));
        data.add(new Wezelek(4, 2));
        data.add(new Wezelek(1, 2));
        data.add(new Wezelek(2, 4));
        data.add(new Wezelek(1, 3));
        data.add(new Wezelek(3, 6));
        data.add(new Wezelek(1, 4));
        data.add(new Wezelek(2, 1));
        data.add(new Wezelek(1, 5));

        //tu ustawiam kolejnosc wprowadzania
        for(int i = 0; i < data.size(); i++) {
            data.get(i).setPozycja(i);
        }

        new Sortowanko(data);

    }

    public Sortowanko(ArrayList<Wezelek> data) {
        //print
        System.out.println("wrzucilem wezly:");
        for(Wezelek n : data) {
            n.print();
        }

        //buduje kopiec MAX
        for(int i = data.size() - 1; i >= 0; i--) {
            data = maxHeapify(data, data.get(i));
        }

        //print
        System.out.println("\nOTRZYMALEM KOPIEC-MAX:");
        for(Wezelek n : data) {
            n.print();
        }

        //sortowanie przez kopcowanie (niestabilne)
        sorted = new ArrayList<Wezelek>();

        int k = data.size();
        for(int i = k; i >=1; i--) {
            Wezelek max = data.get(0);
            Wezelek last = data.get(i-1);

            sorted.add(max);
            data.set(0, last);
            data.remove(i-1);

            if(!data.isEmpty()) {
                maxHeapify(data, data.get(0));
            }
        }

        //print
        System.out.println("STAN PO SORTOWANIU:");
        for(Wezelek n : sorted) {
            n.print();
        }

        //stabilizuje przez zastosowanie algorytmu babelkowego (bo najprostszy w implementacji) na wartosci POZYCJA w nodach
        //zlozonosc O(n^2) - w najgorszym przypadku
        for(int i = 0; i < sorted.size(); i++) {
            for(int j = 0; j < sorted.size(); j++) {
                if( (j+1) != sorted.size() && sorted.get(j).getWartoscX() == sorted.get(j+1).getWartoscX() && sorted.get(j).getPozycja() > sorted.get(j+1).getPozycja()) {
                    Wezelek tmp = sorted.get(j);
                    sorted.set(j, sorted.get(j+1));
                    sorted.set(j+1, tmp);
                }
            }
        }

        //buduje drzewo, czyli przeliczam wartosci ojca i syna i drugiego syna
        buildTree(sorted);

        //print
        System.out.println("stan po ustabilizowaniu:");
        for(Wezelek n : sorted) {
            n.print();
        }
    }

    //tworzy kopiec typu max w wezle root
    public ArrayList<Wezelek> maxHeapify(ArrayList<Wezelek> nodes, Wezelek root) {

        Wezelek left = getLeftNode(nodes, root);
        Wezelek right = getRightNode(nodes, root);
        Wezelek currentNode = root;
        Wezelek max;

        //jezeli lewy wezel jest wsrod wszystkich, i jego wartosc jest wieksza od wartosci roota, to staje sie maxem
        if(nodes.contains(left) && left.getWartoscX() > currentNode.getWartoscX()) {
            max = left;
        } else {
            max = currentNode;
        }

        //to samo dla prawego...
        if(nodes.contains(right) && right.getWartoscX() > max.getWartoscX()) {
            max = right;
        }

        if(max != currentNode) {

            int maxIndex = nodes.indexOf(max),
            currentIndex = nodes.indexOf(currentNode);

            nodes.set(currentIndex, max);
            nodes.set(maxIndex, currentNode);

            maxHeapify(nodes, currentNode);
        }

        return nodes;
    }

    public ArrayList<Wezelek> buildTree(ArrayList<Wezelek> heap) {
        for(int i = 0; i < heap.size(); i++) {
            try {
                heap.get(i).setLewySyn(heap.get(2*i+1));
                heap.get(i).setPrawySyn(heap.get(2*i+2));

                if(i % 2 == 0) {
                    heap.get(i).setOjciec(heap.get(i/2-1));
                } else {
                    heap.get(i).setOjciec(heap.get((int)i/2));
                }
            } catch(Exception e) {
                continue;
            }
        }

        return heap;
    }

    public Wezelek getLeftNode(ArrayList<Wezelek> nodes, Wezelek currentNode) {
        int i = 2 * nodes.indexOf(currentNode) + 1;

        if(i < nodes.size()) {
            return nodes.get(i);
        }

        return null;
    }

    public Wezelek getRightNode(ArrayList<Wezelek> nodes, Wezelek currentNode) {
        int i = 2 * nodes.indexOf(currentNode) + 2;

        if(i < nodes.size()) {
            return nodes.get(i);
        }

        return null;
    }




}
